//Sun Jun 12 16:13:59 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class State{
public:
	int weapons;
	int shots;
	bool operator < (const State &A) const {
		return this->shots > A.shots;
	}
};

class KiloManX {
public:
	int leastShots(vector <string>, vector <int>);
	bool visited[1<<15];
	int N;
};

int KiloManX::leastShots(vector <string> damageChart, vector <int> bossHealth) {
	memset(visited, false, sizeof(visited));
	N = damageChart.size();
	priority_queue<State> q;
	State state = {0, 0};
	q.push(state);
	while(!q.empty()){
		State s = q.top();
		q.pop();
		
		if(visited[s.weapons]) continue;
		visited[s.weapons] = true;
		
		if(s.weapons == (1<<damageChart.size())-1) return s.shots;
		
		for(int i=0; i<damageChart.size(); i++){
			if((s.weapons>>i) & 1) continue;
			int best = bossHealth[i];
			for(int j=0; j<damageChart.size(); j++){
				if(i==j) continue;
				if(((s.weapons>>j) & 1) && damageChart[j][i]!='0'){
					int shotNeeded = (bossHealth[i] + damageChart[j][i] - '1') / (damageChart[j][i] - '0');
					best = min(best, shotNeeded);
				}
			}
			State tmp = {s.weapons | (1<<i), s.shots + best};
			q.push(tmp);
		}
	}
	return -1;
}

//Powered by [KawigiEdit] 2.0!
